BDA_5_1
Obiettivo del text data access è connettere gli utenti con le giuste informazioni al momento giusto.
text data access è un processo che permette di trovare le informazioni contenute in un testo.
la connessione utente - informazione può essere fatta in due modi:
push: il sistema di raccomandazione cerca di fornire le informazioni all'utente, anche senza che quest'ultimo le abbia richieste.
La connessione tra utente e informazione è mediata solitamente da un text retrieval system(serch engine)
è un sistema che permette di trovare i documenti che contengono le informazioni cercate dall'utente.
I motori di ricerca sono usati per fornire raccomandazioni o navigazione.
il text retrieval dal punto di vista dell'utente:
text retrival è un sottotask dell'information retrieval, che è il processo di trovare informazioni (non solo testuali, video , immagini etc...) rilevanti per un utente da una collezione di informazioni.
Il text retrieval dipende dalle query:
Una query di solito è piuttosto breve e incompleta (non è un linguaggio formale come SQL).
Il bisogno di informazione può essere difficile da descrivere precisamente, specialmente quando l'utente non è familiare con l'argomento.
Ciò che conta come risposta corretta è soggettivo
I motori di ricerca sono interrogati con:
C'è una grande dofferenza fra le query usate per fare text retrieval su un search engine e quelle usate per interrogare un database.
Struttura dei dati nei Database:
Struttura dei dati nei motori di ricerca:
Query nei Database:
Query nei motori di ricerca:
I risultati attesi:
Le sfide sono diverse:
nei database:
nei motori di ricerca:
Strategie per il text retrieval nei search engines
Il text retrieval può essere fatto tramite due approcci:
sia $ V = \{ w_1, w_2, ..., w_n\} $ l'insieme di tutti i termini di un vocabolario di un linguaggio naturale.
$ w_i $ è una parola.
sia la query $ q = \{q_1, q_2, ..., q_m\} $ una serie di parole usate per descrivere il contesto di ricerca.
$ q_i \in V $ è una keyword della query.
sia un documento $ D_i = \{d_{i1}, d_{i2}, ..., d_{ik}\} $ una sequenza di parole.
$ d_{ij} \in V $ .
la query $ q $ è sempre più corta di un documento $ D_i $.
$ |q| < |D_i| $.
sia $ C = \{D_1, D_2, ..., D_n\} $ una collezione di documenti.
Obiettivo:
Ottenere un sottoinsieme $ R(q) \subseteq C $ di tutti i documenti che soddisfano la query $ q $.
Realmente si ottiene $R'(q) $ in quanto non si conoscono tutti i documenti rilevanti e quindi tutto $ R(q) $.
quindi $R'(q)$ un'approssimazione di $ R(q) $.
$ R'(q) $ si ottiene con le due strategie:
document selection
document ranking
si implementa un classificatore binario $f(q,d)$ che classifica in:
relevant: $f(q,d) = 1$ se $d \in R(q)$
non relevant: $f(q,d) = 0$ se $d \notin R(q)$
in base alla query $q$.
$R'(q)$ è l'insieme di tutti i documenti classificati come relevant.
$R'(q) = \{d \in C | f(q,d) = 1\}$
si stima la rilevanza assoluta di un documento $d$ per la query $q$.
ogni documento deve essere confrontato con tutti i documenti della collezione per stabilire l'ordine di rilevanza.
si implementa una funzione di ranking $f(q,d) \in \mathbb{R}$ che:
si ordinano i documenti in base al punteggio(ranking) in modo decrescente.
Il set $R(q)$ è parzialmente deciso dal sistema di ranking e parzialmente dall'utente.
l'utente può implicitamente scegliere una soglia $\theta$ e considerare solo i documenti con un punteggio maggiore di $\theta$.
$R'(q)= \{d |f(q,d) \geq \theta\}$
non è necessario confrontare ogni documento con tutti i documenti della collezione.
viene stimata la rilevanza relativa dei documenti e si ordina la collezione in base a se la funzione di ranking di un certo documento è maggiore di quella di un altro
Il Ranking è generalmente preferito perchè la stima della rilevanza relativa è più facile della stima della rilevanza assoluta.
implementare un classificatore binario è più difficile che implementare una funzione di ranking.
difficile di trovare un criterio per classificare la rilevanza di un documento.
probability ranking principle:
1. l'utente visualizza i documenti in maniera sequenziale
2. la rilevanza di un documento è indipendente dalla rilevanza di altri documenti.
Per implementare un search engine è necessario oltre a una strategia di ranking anche un modello che permetta di definire la rilevanza formalmente così da poterla misurare.
Ci sono due famiglie di modelli di retrieval.
La rilevanza di un documento viene calcolata in maniera differente basandosi su due approcci:
1 similarità (Similarity retrieval models)
2 probabilità (Probability retrieval models).
la funzione di ranking di un documento è calcolata in base a una misura di similarità tra la query e il documento.
Vector Space Model fa parte di questa famiglia.
la funzione di ranking di un documento è calcolata in base alla probabilità che il documento sia rilevante per la query.
la query e il documento sono visti come osservazioni di due variabili aleatorie.
Una variabile aleatoria binaria $R$ che indica se un documento è rilevante o meno per una query.
il ranking del documento è la probabilità che $R(q, d) = 1$.
esempi di modelli di retrieval probabilistici sono:
Classic probabilistic model:
Language model:
Divergence from randomness model:
Molti Retrieval models rappresentano il testo di un documento usando un bag of words.
a ogni parola è associato uno score che indica la sua importanza nel documento.
lo score può essere rispetto a:
1: frequenza della parola nel documento.
2: frequenza della parola nella collezione.
3: lunghezza del documento
Queste tre misure cercano di caratterizzare la popolarità del termine nella raccolta e sono combinate per ottenere lo score finale.
con una funzione si determina il contributo complessivo della corrispondenza di una parola, con una correzione per la lunghezza del documento.
La corrispondenza con un termine raro contribuisce maggiormente al punteggio complessivo rispetto alla corrispondenza con un termine comune.
es: data la frase "presidential campaign news",
è un modello di retrieval basato sulla similarità tra la query e il documento
la query e il documento sono rappresentati come vettori di termini.
i vettori possono essere una parola, una frase o un n-gramma di parole.
Se abbiamo un vocabolario di $|V|$ termini(vettori), stiamo definendo uno spazio vettoriale di dimensione $|V|$.
Ogni parola del vocabolario è una base ortogonale dello spazio vettoriale. (sono gli assi dello spazio vettoriale)
la similarità è calcolata in base alla distanza tra i vettori che rappresentano la query e il documento.
i termini del vettore query rappresenta i pesi con cui vengono combinati i termini del vettore documento.
funzione di similarità più semplice è il prodotto scalare tra i vettori.
oppure uso Similarità del coseno
esempio di vector space model tri-dimensionale (vocabolario con 3 parole):
In termini di rappresentazione del documento trascuriamo informazioni come:
l'ordine delle parole
la struttura sintattica
la struttura semantica
è considerato un modello di retrieval semplificato.
Dobbiamo assegnare dei pesi ai termini che rappresentano le componenti dei vettori query e documento.
Dato una vocabolario:
$V = \{w_1, w_2, w_3, ..., w_{|V|}\}$ $ = \{news, about, presidential, campaign, food,...\}$
il vettore di termini di una query $q$ è un vettore binario di dimensione $|V|$.
ogni valore dei vettori $q, d$ se è 1 indica la presenza di una parola di $q$ o $d$ nel vocabolario.
- avrà come valore 1 se il termine è nel vocabolario, 0 altrimenti.
ES:
Si implementa un vector space model per calcolare la rilevanza tra la query $q$ e la collezione $D = \{d_1, d_2, d_3, d_4, d_5\}$
è la funzione di similarità tra la query $q$ e il documento $d_i$.
ci sono dei problemi usando questo semplice modello:
d2 è rilevante come d4
in d4 appare due volte la parola 'presidential' e d2 una sola volta.
d4 dovrebbe essere più rilevante di d2.
Data una query e dei un documenti si usa la frequenza del termine per rappresentare i pesi dei termini.
$ q= (x_1, x_2, ..., x_{|V|})$
$ d= (y_1, y_2, ..., y_{|V|})$
$Sim(q, d) = q \cdot d = \sum_{i=1}^{|V|} x_i \cdot y_i$
'about' non è un termine rilevante per la query come 'presidential' e 'campaign'.
Introduciamo la Inverse Document Frequency
'about' è un termine molto comune nella collezione.
'presidential' e 'campaign' sono termini più rari e quindi più rilevanti.
Si va a pesare la term frequency con la loro inverse document frequency.
$IDF(w) = \frac{M+1}{df(w)}$
$M$: numero di documenti nella collezione.
$df(w)$ è la document frequency:
Penalizza i termini che sono molto frequenti nei documenti della collezione.
per $q$ e $d$ avremo:
$x_i = TF(w_i, q)$,
usando la IDF nel conteggio dei termini nel documento si ottiene un punteggio più alto per i documenti che contengono termini rari nella collezione di documenti.
problema:
es:
TERM FREQUENCY TRANSFORMATION
oppure
$TF(w, d) = 1 + log(1 + c(w, d)$ se $c(w, d) > 0$ altrimenti 0.
il logaritmo è usato per evitare che i termini più frequenti abbiano un peso troppo alto.
le parole con term frequency più alta vanno ad impattare meno sul calcolo della similarità.
BM25 è un altra trasformazione dei pesi dati dalla Term Frequency
$TF(w, d) = \frac{(k + 1) \cdot c(w, d)}{k +c (w, d)}$
Altre trasformazioni della Term Frequency note in letteratura (non da sapere):
Zipf's Law: la frequenza di una parola è inversamente proporzionale al suo rank.
$f_i \propto \frac{1}{r} $
$\rightarrow r\times f =k$
$P(R = 1 | q, d)$
$q$ e $d$ sono modellati come osservazioni della variabile aleatoria $R$.
nella reltà non si ha una tabella con le rilevanze di tutte le possibili combinazioni di $q$ e $d$.
Problema:
Assunzione:
Possiamo calcolare la probabilità che dato un documento che l'utente reputa interessante, $d$ venga ottenuto come risultato di una query $q$.
Si usa quindi l'approssimazione:
$P(R = 1 | q, d) \approx P(q |d, R = 1)$
$P(q |d, R = 1)$:
-probabilità che la query $q$ sia generata da un utente che reputa il documento $d$ rilevante.
$P(R = 1 | d)$:
data una query $q = w_1, w_2, ..., w_n$
Si assume che le parole della query siano statisticamente indipendenti tra loro.
$P(q |d) = P(w_1|d) \cdot P(w_2|d) \cdot ... \cdot P(w_n|d)$
probabilità che la query $q$ sia generata da un utente che reputa il documento $d$ rilevante.
$P(w_i|d)$: probabilità che la parola $w_i$ sia generata dal documento $d$.
nel log space:
ipotesi:
d è un documento ideale che soddisfa la query q fatta dall'utente
le parole della query sono generate da una distribuzione di probabilità $P(w | d)$
un modello fatto cosi è soggetto a questo problema:
Realisticamente:
Soluzione:
Assunzione:
Serve un modello che non assegni probabilità 0 a query che contengono parole che non sono nel documento (unseen words).
Stima della probabilità $P(w | d)$ considerando le unseen words:
Questa stima si calcola tramite un lenaguage model.
Un language model fornisce una distribuzione di probabilità su una sequenza di parole.
Usando la Maximum Likelihood Estimation (MLE): (nel grafico sotto in nero)
$P(w | d) = \frac{c(w, d)}{|d|}$
$c(w, d)$: numero di occorrenze della parola $w$ nel documento $d$.
le parole che non sono nel documento hanno probabilità 0.
Si usa uno smoothed language model per evitare che le parole che non sono nel documento abbiano probabilità 0
viene modellata $P(w | C)$ come probabilità che la parola $w$ sia generata da una collezione di documenti $C$.
le parole che non sono nel documento vengono modellate con probabilità proporzionale alla loro distribuzione nella collezione.
per implementare il modello bisogna sapere come stimare $P(w | C)$
capire come settare il parametro $\alpha_d$
Si vuole assegnare una probabilità ad una frase o ad una parola
UN modello che calcola la probabilità di una frase o di una parola è un Language Model.
$P(W) = P(w_1, w_2, ..., w_n)$ o $P(w_n\ |\ w_1, w_2, ..., w_{n-1})$
$w_i$ è una parola.
$W$ è una frase.
Si calcola la probabilità di una parola w data la sequenza di parole che la precedono h:
$P(w\ |\ h) = \frac{count(h, w)}{count(h)}$
h = “its water is so transparent that”
w = “the”
Questo sistema è utile per i sistemi di correzione ortografica o di completamento automatico.
ma se la frase completa è poco frequente, la probabilità sarà vicina a 0.
ci sono troppi documenti possibili, quindi la probabilità di una frase completa è molto bassa.
frasi simili che differiscono per un sinonimo hanno probabilità molto diverse.
Ricordando che:
$ P(w_1)\cdot P(w_2\ |\ w_1)\cdot P(w_3\ |\ w_1, w_2)\cdot ... \cdot P(w_n\ |\ w_1, w_2, ..., w_{n-1}) $
$ = \prod_{i=1}^{n} P(w_i\ |\ w_1, w_2, ..., w_{i-1})$
Invece di calcolare la probabilià della prossima parola date tutte le parole precedenti, si calcola la probabilità della prossima parola data le ultime $n-1$ parole.
$ P(w_{1},\ldots ,w_{m})\approx \prod _{i=2}^{m}P(w_{i}\mid w_{i-(n-1)},\ldots ,w_{i-1})$
per chiarire se n = 3 and i = 5: (avremo un trigramma)
$ P(w_{i}\mid w_{i-(n-1)},\ldots ,w_{i-1})= P(w_{5}\mid w_{3},w_{4})$
BIGRAMMA
$P(w_i\ | \ w_{i-1})$ , data la parola precedente, calcola la probabilità della parola corrente.
si può estendere a trigrammi, 4-grammi, ecc. per questo si parla di N-gramma.
Di solito è un modello insufficente, perchè non tiene conto del contesto, ovvero delle dipendenze delle parole lontane.
MLE per stimare la probabilità di un n-gramma
MLE è la Maximum Likelihood Estimation.
Dato un bigramma:
la probabilità di una parola data la parola precedente si stima come:
$P_{MLE}(w_i\ |\ w_{i-1}) = \frac{count(w_{i-1}, w_i)}{count(w_{i-1})}$
$count(w_{i-1}, w_i)$: numero di volte che la parola $w_i$ segue la parola $w_{i-1}$.
$count(w_{i-1})$: numero di volte che la parola $w_{i-1}$ appare nel corpus.
MLE N-grams
sia $w^{i-1}_{i-(n-1)} = w_{i-(n-1)},..., w_{i-1}$ una sequenza di parole troncata, allora:
$P_{MLE}(w_i\ |\ w^{i-1}_{i-(n-1)}) = \frac{count(w^{i-1}_{i-(n-1)}, w_i)}{count(w^{i-1}_{i-(n-1)})}$
$count(w^{i-1}_{i-(n-1)}, w_i)$:
$count(w^{i-1}_{i-(n-1)})$:
suppenendo che dal modello bigramma si ottengano le seguenti probabilità:
se vogliamo calcolare la probabilità della frase:
$(<s>$ I want english food $</s>)$
$P(</s>$ I want english food $</s>) = $
$$= P(I|<s>) \times P(want|I) \times P(english|want) \times P(food|english) \times P(</s>|food) = $$$$ = 0.25 × 0.33 × 0.0011 × 0.5 × 0.68 = 0.000031 $$$$\prod_{i=1}^{n} P(w_i\ |\ w_1, w_2, ..., w_{i-1}) \rightarrow 0$$Overfitting nell'N-gram Language Model
N-gram stima delle buone probabilità solo se il corpus di test è simile al corpus di training.
nella pratica, il corpus di training è sempre troppo piccolo per coprire tutte le possibili frasi.
se nel corpus di train non c'è una frase $w^{n-1}$
serve una tecnica per stimare la probabilità di una frase che non è presente nel corpus di training.
Laplace Smoothing
aggiungo 1 a tutti i conteggi.
$P_{Laplace}(w_i\ |\ w^{i-1}_{i-(n-1)}) = \frac{count(w^{i-1}_{i-(n-1)}, w_i) + 1}{count(w^{i-1}_{i-(n-1)}) + |V|}$
Il laplace smoothing è una approssimazione della probabilità reale. In verità va a modificare la distribuzione di probabilità degli n-grammi.
vediamo un esempio di costruzione di bigrammi su un certo corpus di testo:
calcolo la probabilità di ogni bigramma.
invertendo il processo:
ritorno dalla probabilità al conteggio con la formula:
$ count^*(w_{i-1}, w_i) = [count(w_{i-1}, w_i) + 1] \times \frac{count(w_{i-1})}{count(w_{i-1}) + |V|}$
Un search engine è un informazione retrieval system che permette di trovare informazioni fra un insieme di dati di vario tipo, fra cui testi, immagini, video, ecc.
Abbiamo parlato in particolare del 'text retrieval':
strategie di retrieval;
retrieval models;
language models;
Un informazione retrieval system è composto da 4 componenti:
è il primo step di ogni task di text mining.
divide il testo in token (parole, simboli, ecc.).
determina come rappresentare i documenti.
Serve per permettere ad un search engine di poter indicizzare moli di dati più grandi di quanto possano essere caricati nella memoria del sistema.
è inefficiente fare lo scan di tutto il corpus per ogni query.
Un sistema di indexing carica una porzione del corpus in memoria
crea un indice che permette di trovare rapidamente i documenti che contengono un certo token.
Viene usata una struttura dati chiamata inverted index:
per ogni documento viene salvata la lista dei token che contiene e associato un Document ID.
si crea una tabella che raggruppa tutti i token estratti dai documenti ordinati per Document ID.
si ordinano i token in ordine alfabetico
si contano i token uguali con stesso Document ID
vengono raggruppati i token uguali con stesso Document ID
si aggiunge alla tabella una colonna con la document frequency (DF) del token
il file viene quindi diviso in:
dictionary:
postings file:
Funzione che Permette al Retrieval System di assegnare uno score a ogni documento per ogni query in modo efficiente
si può fare con un inverted index.
fornisce le informazioni necessarie per calcolare lo score di ogni documento per ogni query.
esempio di Ranker: Scorer term at a time Ranking
Si aggiunge un ulteriore step al retrieval system per migliorare la qualità dei risultati.
Si aggiungono informazioni sulle query per migliorare la qualità dei risultati.
Le informazioni possono essere:
implicite:
tutte le informazioni che si possono ricavare dall'interazione dell'utente con il sistema.
es. tempo speso su una pagina, click, scroll, ecc.
Diversi tipi di feedback:
l'utente può dire quali risultati sono rilevanti o meno.
tali risultati sono usati dal sistema per la Query Expansion
se l'utente dice che un documento è rilevante, si può usare il contenuto del documento per espandere la query.
si aggiungono i termini più frequenti del documento alla query.
si usano i primi k risultati della query come feedback.
questi k risultati sono usati come query expansion.
non sempre è possibile avere feedback espliciti dall'utente.
è possibile avere feedback impliciti dall'utente.
Si basa sui dati raccolti nell'interazione fra l'utente e il sistema.
Il VSM fornisce la rilevanza di un documento per una query.
Si vuole usare il feedback per espandere la query (la query viene modificta in base al feedback).
é il sistema di feedback basato su VSM.
tramite la funzione di similarità si calcola la distanza fra la query e i documenti.
si individuano i documenti più simili alla query.
si calcola il centroide dei documenti top ranked.
si calcola il centroide dei documenti non rilevanti.
geometricamente:
il vettore query risultante sarà:
$ q_m = \alpha q_0 + \beta \frac{1}{|D_r|} \sum_{d \in D_r} d - \gamma \frac{1}{|D_{nr}|} \sum_{d \in D_{nr}} d $
i termini dei documenti rilevanti avranno un peso maggiore dei termini dei documenti non rilevanti nel mofiicare la query originale.
Esempio:
potenziali problemi:
costo computazionale elevato
considerando solo i documenti rilevanti avremo pochi termini per espandere la query.
la media dei documenti non rilevanti può aver contenuto informativo utile per espandere la query.
overfitting:
per evitare l'overfitting
abbiamo bisogno di un numero sufficiente di documenti rilevanti per espandere la query.
è importante tenere conto della query originale.
La classificazione dei testi è il processo di assegnazione di categorie di soggetti, argomenti o generi a un dato documento.
Può essere utilizzata per:
I metodi di classificazione:
Supervised Machine Learning
Input:
Output:
a learned classifier f: D -> C
classifictori:
si riferisce a qualsiasi processo computazionale che coinvolge il significato delle parole.
Comprende compiti quali
Lemma: è la forma base di una parola.
For example, "car" is a hyponym of "vehicle"
Le relazioni tassonomiche si riferiscono all'organizzazione gerarchica delle parole in categorie.
Le relazioni tra parole o sensi possono essere classificate in diverse categorie:
I sinonimi sono parole che hanno lo stesso o quasi identico significato,
Gli antonimi sono parole con significato opposto.
Gli iponimi sono parole più specifiche di un'altra parola
Gli ipernimi sono parole più generali.
Anche la parentela e la somiglianza tra parole sono concetti importanti per comprendere le relazioni tra le parole.
La semantica vettoriale e la disambiguazione del senso delle parole sono due metodi utilizzati per rappresentare e distinguere i diversi significati delle parole.
Dictionary-based approach
Vector-semantics approach
I dizionari contengono definizioni di parole:
sono contenuti su appositi database.
non è facile da estendere ad altre lingue.
andrebbe aggiornato continuamente per star dietro all'evoluzione della lingua.
per risolvere problemi come la circolarità delle definizioni
si usa la semantica lessicale, che studia il significato delle parole e le loro relazioni, come i sinonimi e i contrari.
Anche il contesto in cui le parole si trovano può fornire indizi sul loro significato
es. WordNet
WordNet è un dizionario lessicale per l'inglese.
i metodi basati su dictionary neccessitano di un processo di disambiguazione del senso delle parole (Word sense disambiguation, WSD)
si vuole determinare il significato corretto di una parola nel contesto, dato un inventario fisso di potenziali sensi della parola.
es.
"The bank of the river was covered with dead fish"
utilizzata in diverse applicazioni,
come:
tecniche di Word sense Disambiguation
utilizza un insieme di dati etichettati in base al loro 'significato' per addestrare un classificatore che predirrà la classe(significato) di una parola in un determinato contesto.
Estrazione delle caratteristiche:
Collocational features
Bag of words features
non considera la posizione delle parole vicine rispetto alla parola target.
prende un set di parole nello stesso corpus della parola target e le utilizza come caratteristiche per il classificatore.
può tenere conto della:
I Thesaurus methods sono un'alternativa agli algoritmi supervisionati per la disambiguazione del senso quando i dati di addestramento etichettati sono limitati e costosi.
Questi metodi utilizzano dizionari e tesauri o basi di conoscenza simili per una supervisione indiretta.
sono detti a supervisione debole
es: disambiguazione di 'bank' con WordNet
nella frasse troviamo parole usate per definire bank $^1$
bank $^1$ sarà il significato di 'bank' nella frase.
Algoritmo basato su dizionari per la disambiguazione di senso:
sceglie il senso la definizione del dizionario condivide il maggior numero di parole con la parola target.
Lesk semplificato sembra funzionare meglio di altri di quello originale.
le tecniche di word disambiguation basate sui dizionari sono limitate dalla disponibilità di dizionari e dalla loro copertura.
Si passa da una semantica lessicale a una semantica vettoriale, che rappresenta le parole come vettori numerici n-dimensionali.
La semantica vettoriale è basata sull'ipotesi distribuzionale, che afferma che il significato di una parola è determinato dal suo contesto.
il processo di rappresentazione delle parole come vettori è chiamato word embedding.
Si modella il significato delle parole embeddandole in uno spazio vettoriale.
le parole sono rappresentate da vettori di dimensione fissa.
Le parole nello stesso contesto tendono ad avere significati simili.
I vector semantic models possono essere appresi automaticamente dal testo senza alcuna etichettatura o supervisione complessa
mentre in molte applicazioni di linguistica computazionale il significato delle parole è rappresentato da un indice di vocabolario o "numero di parole".
I modelli di semantica vettoriale possono fornire una rapprentazione sparsa o densa delle parole.
Rappresentazione vettoriali sparse
vettori grandi e con molti zeri
Matrici di co-occorrenza basate su:
Rappresentazione vettoriali dense
vettori piccoli e con pochi zeri
Algoritmi di riduzione della dimensionalità
Single Value Decomposition (SVD) è utilizzato per ridurre la dimensione di una matrice di parole.
Modelli di Word Embedding basati su reti neurali (Neural language models)
forniscono embedding statici delle parole
Word2Vec
forniscono embedding dinamici delle parole
- il modello è allenato per prevedere la parola successiva in base alle seqquenze di parole precedenti, che sono il contesto della parola target.
mostra la frequenza di occorrenza di una parola in un documento
raw are words in the vocabulary
$M_{|v|\times|d|}$
due documenti sono simili se i vettori colonna sono simili
due parole sono simili se i vettori riga sono simili
rappresentazione matematica di un corpus testuale che mostra la frequenza di co-occorrenza delle parole e del loro contesto.
le righe rappresentano le parole ;
le colonne il contesto.
le parole e il contesto sono i due componenti principali che vengono utilizzati per calcolare la frequenza di co-occorrenza.
$M_{|v|\times|v|}$
$|V|$ è la dimensione del vocabolario;
ogni parola avrà $|V|$ componenti nel vettore;
le componenti del vettore saranno per lo più 0;
Dot Product
il prodotto scalare tra due vettori:
$v \cdot w = \sum_{i=1}^{n} v_i w_i$
tende a dare risultati più alti quando i vettori hanno valori alti nelle stesse dimensioni.
favorisce in generale i vettori con pochi zeri e valori alti.
favorisce quindi le parole più frequenti.
non è una buona misura di similarità tra parole.
Cosine Similarity
a partire dal dot product si può calcolare la cosine similarity tra due vettori:
$a \cdot b = ||a|| \cdot ||b|| \cdot cos(\theta)$
$cos(\theta) = \frac{a \cdot b}{||a|| \cdot ||b||}$
la similarità coseno tra due vettori:
$cos(v,w) = \frac{v \cdot w}{||v|| \cdot ||w||}$ $= \frac{\sum_{i=1}^{n} v_i w_i}{\sqrt{\sum_{i=1}^{n} v_i^2} \sqrt{\sum_{i=1}^{n} w_i^2}}$
le frequenze di co-occorrenza sono non negativi, quindi la cosine similarity per i vettori della matrice termine-termine varia da 0 a 1.
es:
Le matrici di co-occorrenza sono spesso molto grandi e sparse.
La term frequency può essere utile per avere info sul contesto di una parola.
non è abbastanza perchè le parole comuni hanno frequenze elevate e non sono utili per la disambiguazione del senso.
la soluzione è utilizzare: la term-frequency - inverse document frequency (tf-idf) come pesi dei vettori.
Tf-idf come misura per la matrice di co-occorrenza delle parole.
penalizza le parole che sono comuni in tutti i documenti.
per la parola $t$ nel documento d:
$w_{t, d} = TF_{t, d} \times IDF_{t}$
frequenza della parola w nel documento d:
$TF_{w, d} = count(w, d) $
(approx. in log space)
$= log(1 + count(w, d))$
inverse document frequency della parola w:
$ IDF_{w} = log(\frac{N}{DF_{w}})$
$DF_{w}$ = numero di documenti che contengono la parola w
$N$ = numero totale di documenti della collezione
Misura se due variabili co-ooccorrono più spesso di quanto ci si aspetterebbe appaiano indipendentemente.
$PMI(w1, w2) = log(\frac{P(w1, w2)}{P(w1)P(w2)})$
quando $\frac{P(w1, w2)}{P(w1)P(w2)} < 1$ le due variabili non sono indipendenti
si sostitscono i valori negativi con 0
es:
tf-idf (or PMI) vectors are
◦ long (length |V|= 20,000 to 50,000)
◦ sparse (most elements are zero)
Alternative: learn vectors which are ◦ short (length 50-1000)
◦ dense (most elements are non-zero)
La Decomposizione ai Valori Singolari (SVD) è un metodo che permette di riurre la dimensionalità di una matrice in un numero minore di dimensioni. Ciò viene fatto attraverso una rotazione degli assi in direzione della maggior varianza dei dati. In altre parole, la SVD trova le dimensioni più importanti di un dataset, cioè quelle lungo le quali i dati variano di più.
Oss:
la SVD si basa sulla fattorizzazione di una matrice in 3 matrici
Si può pensare alla SVD come ad una generalizzazione della PCA, in quanto la PCA è un caso particolare della SVD.

dove:
i vettori singolari sinistri e destri sono ortogonali tra loro
$\sigma_i$ sono valori scalari, detti valori singolari
i vettori singolari sinistri $u_i$ sono vettori di dimensione $m$
i vettori singolari destri $v_i$ sono vettori di dimensione $n$
L'SVD può essere applicata alla matrice termine-contesto, che rappresenta le frequenze di ogni parola in un contesto specifico.
L'SVD suddivide questa matrice in tre matrici quadrate: una matrice di parole $W$, una matrice di valori singolari $\Sigma$ e una matrice di contesti $C$.
Ogni riga della matrice $W$ rappresenta una parola
le colonne rappresentano dimensioni latenti
La matrice $C$ è la matrice di contesti, che rappresenta le frequenze di ogni contesto in cui una parola appare.
Ogni riga della matrice $C$ rappresenta ora le nuove dimensioni latenti
le colonne rappresentano i contesti specifici.
Oss: $W==U$
Oss: $C==V$
utilizza solo le prime k dimensioni delle tre matrici quadrate utilizzate per suddividere la matrice termine-contesto iniziale.
In questo modo la matrice $W$ ha dimensione $|V| \times k$,
e ogni riga rappresenta una parola come un vettore denso k-dimensionale (embedding).
la nuova matrice approssimata rappresenta l'informazione più importante della matrice originale,
Oss: I valori singolari nella matrice $\Sigma$ rappresentano l'importanza relativa delle diverse dimensioni nella rappresentazione della matrice termine-contesto. I valori singolari più grandi rappresentano le dimensioni che contengono la maggior quantità di varianza nei dati e sono quindi le dimensioni più importanti per la rappresentazione della matrice termine-contesto.
Oss: In genere, valori singolari e autovalori sono concetti distinti.
LSA è una tecnica usata in NLP in particolare nella semantica distributiva , per analizzare le relazioni tra un insieme di documenti e i termini che contengono producendo un insieme di concetti relativi ai documenti e ai termini.
le parole che hanno un significato vicino ricorreranno in parti di testo simili (l' ipotesi distributiva ).
Una matrice contenente i conteggi delle parole per documento (le righe rappresentano parole univoche e le colonne rappresentano ciascun documento)
costruita da una grande porzione di testo
viene utilizzata la SVD per ridurre il numero di righe preservando la struttura di somiglianza tra le colonne.
I documenti vengono quindi confrontati per somiglianza del coseno tra due colonne qualsiasi. I valori vicini a 1 rappresentano documenti molto simili mentre i valori vicini a 0 rappresentano documenti molto diversi.
Si vuole predire quanto è probabile che una parola appaia in un contesto specifico.
non si assegnano score di probabilità alle parole più probabili (classificazione multi-classe)
il problema di predizione delle parole viene trasformato in un problema di classificazione binaria.
come classificatore si usa la logistic regression
Invece di contare quanto spesso w1 e w2 appaiono insieme
si addestra un classificatore binario per predire se w2 è una parola vicina a w1 o meno.
Si usa un approccio di apprendimento self-supervised
Una parola di contesto c che si trova vicino ad una parola target w nel corpus è la "risposta corretta" per l'apprendimento supervisionato.
Non c'è bisogno di etichette umane
le possibili implementazioni sono due:
The skip-gram with negative sampling algorithm (skip-gram or SGNS) è un algoritmo di apprendimento self-supervised per l'apprendimento di word embeddings.
la parola target w e le parole di contesto vicine sono visti come esempi positivi
si campionano casualmente alcune parole dal vocabolario per creare esempi negativi
si addestra un classificatore binario(LR) basato su Logistic Regression
la probabilità che una parola c sia vicina a una parola target w è basata sulla similarità calcolata come prodotto scalare tra i due vettori di embedding
$$Similarity(w,c) \approx w^Tc$$
$$P(+|w,c) = \sigma(w^Tc) = \frac{1}{1+e^{-w^Tc}}$$
$$P(-|w,c) = 1 - \sigma(w^Tc) = \frac{1}{1+e^{w^Tc}}$$
nello skip-gram si assume che le parole di contesto siano indipendenti tra loro
$$P(+|w,c_1,c_2,...,c_{2m}) = \prod_{j=1}^{2m} P(+|w,c_j)$$
in log space
$$log P(+|w,c_1,c_2,...,c_{2m}) = \sum_{j=1}^{2m} log P(+|w,c_j)$$
il classifcatore apprende due matrici di embedding
le matrici contengono un embedding per ogni parola nel vocabolario
ogni parola avrà due embedding in base a se è una parola di contesto o una parola target
alleniamo con esempi positivi e negativi
per ogni istanza di training (w,c)
la funzione viene ottimizata tramite discesa del gradiente
ad ogni iterazione si aggiornano i parametri di embedding
per la parola target w:
Le parole embeddate possono essere combinate con per ottenere analogie tra i significati delle parole